package offer.tree;

import java.util.Stack;

/**
 * @author DengYuan2
 * @create 2021-03-01 19:06
 */
public class n_36 {
    public static void main(String[] args) {
        n_36 n = new n_36();
        TreeNode t1 = new TreeNode(10);
        TreeNode t2 = new TreeNode(6);
        TreeNode t3 = new TreeNode(14);
        TreeNode t4 = new TreeNode(4);
        TreeNode t5 = new TreeNode(8);
        TreeNode t6 = new TreeNode(12);
        TreeNode t7 = new TreeNode(16);
        t1.left=t2;
        t1.right=t3;
        t2.left=t4;
        t2.right=t5;
        t3.left=t6;
        t3.right=t7;
        TreeNode treeNode = n.Convert2(t1);
        System.out.println(treeNode);

    }

    /**
     * @param pRootOfTree
     * @return
     */
    TreeNode pre = null;
    TreeNode head = null;
    public TreeNode Convert(TreeNode pRootOfTree) {
        if (pRootOfTree==null){
            return null;
        }
        helper(pRootOfTree);
        return head;

    }

    public void helper(TreeNode node){
        if (node==null){
            return;
        }
        helper(node.left);
        node.left=pre;
        if (pre!=null){
            pre.right=node;
        }
        pre=node;
        if (head==null){
            head=node;
        }
        helper(node.right);
    }

    /**
     * 中序遍历
     * @param root
     */
    public void inOrder(TreeNode root){
        TreeNode node =root;
        Stack<TreeNode> stack = new Stack<>();
        while (node!=null || !stack.isEmpty()){
            while (node!=null){
                stack.push(node);
                node=node.left;
            }
            node = stack.pop();
            if (node.right!=null){
                node=node.right;
            }
        }


    }


    TreeNode preNode=null;
    TreeNode headNode=null;
    public TreeNode Convert2(TreeNode pRootOfTree) {
        if (pRootOfTree==null){
            return null;
        }
        Stack<TreeNode> stack = new Stack<>();
        TreeNode cur=pRootOfTree;
        //找到最左节点
        while (cur!=null){
            headNode= cur;
            cur=cur.left;
        }
        cur=pRootOfTree;
        while (cur!=null || !stack.isEmpty()){
            while (cur!=null){
                stack.push(cur);
                cur=cur.left;
            }
            TreeNode now = stack.pop();
            if (preNode!=null){
                preNode.right=now;
            }
            now.left=preNode;
            preNode=now;
            cur=now.right;
        }
        return headNode;
    }

}
